/*
    begin 2024.11.23.19.40
    20pts 20.29
*/
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

const ll maxn{ll(1e5+5)};
ll c,t,n,m,vi[maxn],vj[maxn],inf{ll(1)<<60},tmp;
char v[maxn];

namespace s1{
    char cc[]{'T','F','U'};
    char a[maxn];
    char b[maxn];
    char cxor(char const &c){
        if(c=='T')return 'F';
        else if(c=='F')return 'T';
        else return 'U';
    }
    ll ans{inf};
    void dfs(ll const& d){
        if(d>n){
            for(ll i{1};i<=n;i++)b[i]=a[i];
            for(ll i{1};i<=m;i++){
                if(v[i]=='T'||v[i]=='F'||v[i]=='U'){
                    b[vi[i]]=v[i];
                }else if(v[i]=='+'){
                    b[vi[i]]=b[vj[i]];
                }else{
                    b[vi[i]]=cxor(b[vj[i]]);
                }
            }
            ll sum{};
            for(ll i{1};i<=n;i++){
                if(a[i]!=b[i]){
                    return;
                }
                if(a[i]=='U')sum++;
            }
            ans=min(ans,sum);
            return;
        }
        for(auto const& i:cc){
            a[d]=i;
            dfs(d+1);
        }
    }
}

namespace s2{
    char c[maxn];
}
namespace s3{
    char c[maxn];
    struct USF{
        ll f[maxn];
        USF(){
            for(ll i{1};i<=n;i++){
                f[i]=i;
            }
        }
        ll find(ll const&u){
            if(f[u]==u)return u;
            return f[u]=find(f[u]);
        }
        void merge(ll const &u,ll const &v){
            f[find(u)]=find(v);
        }
    }usf;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>c>>t;
    if(c<=2){
        while(t--){
            cin>>n>>m;
            for(ll i{1};i<=m;i++){
                cin>>v[i];
                if(v[i]=='T'||v[i]=='F'||v[i]=='U'){
                    cin>>vi[i];
                }else{
                    cin>>vi[i]>>vj[i];
                }
            }
            s1::ans=inf;
            s1::dfs(1);
            cout<<s1::ans<<'\n';
        }
    }else if(c==3||c==4){
        while(t--){
            cin>>n>>m;
            ll ans{};
            fill(s2::c,s2::c+1+n,'T');
            for(ll i{1};i<=m;i++){
                cin>>v[i];
                cin>>tmp;
                s2::c[tmp]=v[i];
            }
            for(ll i{1};i<=n;i++){
                if(s2::c[i]=='U')ans++;
            }
            cout<<ans<<'\n';
        }
    }else if(c==5||c==6){
        while(t--){
            cin>>n>>m;
            memset(s3::c, 'T', sizeof(s3::c));
            
            ll ans{};
            for(ll i{1};i<=m;i++){
                cin>>v[i];
                if(v[i]=='U'){
                    cin>>tmp;
                    s3::c[tmp]='U';
                }else{
                    cin>>vi[i]>>vj[i];
                    s3::usf.merge(vi[i],vj[i]);
                    s3::c[vi[i]]=s3::c[vj[i]];
                }
            }
            unordered_map<ll,pair<ll,bool>> mm;
            for(ll i{1};i<=n;i++){
                mm[s3::usf.find(i)].first++;
                if(s3::c[i]=='U'){
                    mm[s3::usf.find(i)].second=true;
                }
            }
            for(auto [k,v]:mm){
                if(v.second){
                    ans+=v.first;
                }
            }
            cout<<ans<<'\n';
        }
    }
    // else if(c==7||c==8){

    // }
}